Démonstration de l'existence du PGCD

Propriété-définition

Soit \(a \in \mathbb{Z}\) et \(b \in \mathbb{Z}\) tels que \((a;b) \neq (0;0)\) .

L'ensemble \(\mathscr{D}(a;b)\) contient un plus grand élément, noté \(\mathrm{PGCD}(a;b)\) , et appelé plus grand commun diviseur de \(a\) et de \(b\) .

Démonstration

L'ensemble \(\mathscr{D}(a;b)\) est non vide et majoré dans \(\mathbb{Z}\) . En effet :

• \(1\) divise \(a\) et \(b\) , donc \(1 \in \mathscr{D}(a;b)\) , et donc \(\mathscr{D}(a;b) \neq \varnothing\) .
• Si \(d \in \mathscr{D}(a;b)\) , alors \(d\) appartient à \(\mathscr{D}(a)\) et à \(\mathscr{D}(b)\) .
  Or, comme \(a\) ou \(b\) n'est pas nul, l'un de ces deux ensembles est fini et majoré (par \(\left\vert a \right\vert\) ou \(\left\vert b \right\vert\) ). Ainsi, \(d \leqslant \max(\left\vert a \right\vert;\left\vert b \right\vert)\) et donc \(\mathscr{D}(a;b)\) est majoré.
  

Or, tout ensemble non vide et majoré dans \(\mathbb{Z}\) admet un plus grand élément, ce qui prouve l'existence de \(\mathrm{PGCD}(a;b)\) .

Remarques

• Par convention, on choisit que \(\mathrm{PGCD}(0;0)=0\) .
• Pour tout  \(a \in \mathbb{Z}\) et \(b \in \mathbb{Z}\) tels que \((a;b) \neq (0;0)\) , on a \(1 \in \mathscr{D}(a;b)\) .
  On en déduit que \(\mathrm{PGCD}(a;b) \geqslant 1\) , c'est-à-dire \(\mathrm{PGCD}(a;b) \in \mathbb{N}^\ast\) .
• Pour tout  \(a \in \mathbb{Z}\) et \(b \in \mathbb{Z}\) , \(\mathrm{PGCD}(a;b)=\mathrm{PGCD}(b;a)\) .